/**
 * https://leetcode.cn/problems/generate-parentheses/
 * 解题方法：
 * 1.递归+剪分支
 * 
 * 解题思路：
 * 1.先把所有可能的组合用递归实现
 * 2.把不符合要求的分支去除,加open和close计数器.
 * 
 * 优化：
 * 把判断写在传递前
 * 
 */


/**
 * 
 * 速度 80ms O(n)
 * @param {number} n 多少对括号
 * @return {string[]}
 */
var generateParenthesis = function(n) {
    let res=[];
    if(n<1) return [];
    dfs2(n,'',res,0,0);
    
    return res;
};

function dfs(n=0,path='',res=[],open=0,close=0){
    // 剪分支：无效的分支： 开括号不能大于，尾括号数不能大于开括号数
    if(open>n || close>open){
        return
    }
    //长度大于 括号总数就回溯
    if(path.length>=n*2){
        res.push(path)
        return ;
    }
    dfs(n,path+'(',res,open+1,close);
    dfs(n,path+')',res,open,close+1);
}


function dfs2(n=0,path='',res=[],open=0,close=0){
    // 剪分支：无效的分支： 开括号不能大于，尾括号数不能大于开括号数
    // if(open>n || close>open){
    //     return
    // }
    //长度大于 括号总数就回溯
    if(path.length>=n*2){
        res.push(path)
        return ;
    }
    // 开括号要小于总数
    if(open<n){
        dfs2(n,path+'(',res,open+1,close);
    }
    // 闭括号必须小于开括号
    if(close<open){
        dfs2(n,path+')',res,open,close+1);
    }
    
}


console.log(generateParenthesis(4))